import java.util.Random;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 17655
 * Date: 2024-12-21
 * Time: 10:57
 */
public class test3 {
    /*
    LeetCode 面试题17,14 最小K个数
     */

    // 快速选择算法
    public int[] smallestK(int[] nums, int k) {
        qsort(nums,0,nums.length-1,k);

        int[] ret = new int[k];
        for(int i=0;i<k;i++){
            ret[i] = nums[i];
        }
        return ret;
    }

    public void qsort(int[] nums,int l ,int r,int k){
        if(l>=r){
            return;
        }
        int key = nums[new Random().nextInt(r-l+1)+l];
        int right = r+1;
        int left = l-1;
        int i = l;
        while(i<right){
            if(nums[i]<key){
                swap(nums,++left,i++);
            }else if(nums[i]==key){
                i++;
            }else{
                swap(nums,--right,i);
            }
        }
        // 进行分类
        int a = left - l+1;
        int b = right - left -1;
        if(a>k){
            qsort(nums,l,left,k);
        }else if(a+b>=k){
            return ;
        }else{
            qsort(nums,right,r,k-a-b);
        }
    }


    public void swap(int[] nums,int left,int right){
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;
    }
}
